package leetcode.dp;

public class UniquePathsII63 {
    class Solution1 {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
                return 0;
            }
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (obstacleGrid[i][j] != 1) {
                        if (i != 0 && j != 0) {
                            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                        } else if (i != 0) {
                            dp[i][j] = dp[i - 1][j];
                        } else if (j != 0) {
                            dp[i][j] = dp[i][j -1];
                        }
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
    }

    class Solution2 {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
                return 0;
            }
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[] dp = new int[n];
            dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (obstacleGrid[i][j] != 1) {
                        if (i != 0 && j != 0) {
                            dp[j] += dp[j - 1];
                        } else if (j != 0) {
                            dp[j] = dp[j - 1];
                        }
                    } else {
                        dp[j] = 0;
                    }
                }
            }
            return dp[n - 1];
        }
    }

    class Solution3 {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
                return 0;
            }
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m + 1][n + 1];
            dp[0][1] = obstacleGrid[0][0] == 1 ? 0 : 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (obstacleGrid[i - 1][j - 1] != 1) {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            return dp[m][n];
        }
    }

    class Solution4 {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
                return 0;
            }
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[] dp = new int[n + 1];
            dp[1] = obstacleGrid[0][0] == 1 ? 0 : 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (obstacleGrid[i - 1][j - 1] != 1) {
                        dp[j] += dp[j - 1];
                    } else {
                        dp[j] = 0;
                    }
                }
            }
            return dp[n];
        }
    }
}
